package xiaohong.search;

import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Date;
import java.util.List;

import static xiaohong.sort.RadixSortDemo.radixSort;

public class SearchDemo {

    public static void main(String[] args) {
        int[] nums = new int[10];
        for (int i = 0; i < 10; i++) {
            nums[i] = (int)(Math.random() * 100);
        }
        nums[9] = 15;
        nums[8] = 15;
        radixSort(nums);
        System.out.println("数组" + Arrays.toString(nums));
        List<Integer> integers = twoSearch(nums, 0, nums.length - 1, 15);
        System.out.println(integers);

//        List<Integer> list = new ArrayList<>(100001);
//        for (int i = 0; i < 100001; i++) {
//            list.add((int)(Math.random() * 1000000));
//        }
//        // 分割集合
//        int batchSize = 2000;
//        List<List<Integer>> lists = splitList(list, batchSize);
//        System.out.println(lists.size());
    }

    public static <T> List<List<T>> splitList(List<T> list, int batchSize) {
        List<List<T>> subLists = new ArrayList<>();
        for (int i = 0; i < list.size(); i += batchSize) {
            int endIndex = Math.min(i + batchSize, list.size());
            subLists.add(list.subList(i, endIndex));
        }
        return subLists;
    }

    public static List<Integer> twoSearch(int[] nums , int left , int right , int target) {
        if (left > right) {
            return new ArrayList<>();
        }
        int mid = (right + left ) / 2;
        int midVal = nums[mid];

        if (midVal > target){
            return twoSearch(nums, left, mid - 1, target);
        }else if (midVal < target){
            return twoSearch(nums, mid + 1, right, target);
        }else {
            List<Integer> list = new ArrayList<>();
            int temp = mid - 1;
            while (true) {
                if (temp < 0 || nums[temp] != midVal){
                    break;
                }
                list.add(temp);
                temp--;
            }
            list.add(mid);
            temp = mid + 1;
            while (true) {
                if (temp > nums.length - 1 || nums[temp] != midVal){
                    break;
                }
                list.add(temp);
                temp++;
            }
            return list;
        }
    }



}
